//https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=13&tqId=1377477&ru=%2Fpractice%2F253d2c59ec3e4bc68da16833f79a38e4&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 链表中倒数最后k个结点
// 思路1:双指针问题，1.先让快指针走n步；2.然后让快慢指针同时走，直到快指针指向nullptr时，慢指针就是第k个元素
// 思路2:栈问题，使用栈；

// 扩展题目，链表中的中间节点
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <set>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        //快指针先行k步
        for(int i = 0; i < k; i++){ 
            if(fast != NULL)
                fast = fast->next;
            //达不到k步说明链表过短，没有倒数k
            else
                return slow = NULL;
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};